package Test;

import java.util.*;

import java.util.Arrays;
import java.util.Comparator;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;

class Main6 {
    //长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0 ;
        int r = 0 ;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;
        int len = nums.length;
        // for( ; r < len ; r++){
        while(r < len){
            sum+=nums[r] ;
            while(sum >= target){
                // sum-=nums[l];
                // l++;
                // if(sum >= target)
                minLen = Math.min(minLen , r - l  + 1);
                sum-=nums[l];
                l++;
            }
            r++;
        }
        return minLen == Integer.MAX_VALUE ? 0 : minLen;
    }
    //x的平方根
    public int mySqrt(int x) {
        //处理一个细节问题
        //但是在我们的题目范围中x大于等于0,不必考虑下面的一行代码
        if(x < 0) return 0;
        long left = 0;
        long right = x;
        while(left < right){
            long mid = left + (right - left + 1)/2;
            //下面的if中是这道题的条件,因为是求x的平方根
            if(mid * mid <= x) left = mid;
            else right = mid - 1;
        }
        return (int)left;
    }
    //跳跃游戏(贪心算法)
    public boolean canJump(int[] nums) {
        int n = nums.length;
        //定义可以到达的最大位置
        int max = 0;
        for(int i = 0;i<n;i++){
            //i是自己本来的位置,小于最大位置的时候,才能移动
            if(i <= max){
                max = Math.max(max,i+nums[i]);
                if(max >= n - 1) return true;
            }
        }
        return false;

    }
    public static void main12(String[] args) throws ExecutionException, InterruptedException {

        Callable<Integer> callable = new Callable<Integer>() {
            @Override
            public Integer call() throws Exception {
                int count = 0;
                while(count < 1000){
                    count++;
                }
                return count;
            }
        };
        FutureTask<Integer> futureTask = new FutureTask<>(callable);
        Thread t = new Thread(futureTask);
        t.start();
        System.out.println(futureTask.get());
    }
    public static void main11(String[] args) {
        String salt = UUID.randomUUID().toString().replace("-", "");
        System.out.println(salt.length());
    }
    public static void main10(String[] args) {
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(1,1);
        map.put(2,2);
        map.put(3,3);
        map.put(4,4);
        for(Integer x : map.keySet()){
            System.out.println("key:"+x+"-value:"+map.get(x));
        }
    }
    public static void main9(String[] args) {
        HashSet<Integer> set = new HashSet<>();
        set.add(1);
        set.add(2);
        set.add(3);
        set.add(4);
        for(Integer x : set){
            System.out.println(x);
        }
    }
    public static void main8(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = new int[]{1,2,3,4,5,6};
        int n = 6;
        int input = sc.nextInt();
        input = input % n;
        int r = n - input;
        int[] newArr = new int[n];
        for(int i = 0;i<n;i++){
            r = r % 6;
            newArr[i] = nums[r++];
        }
        System.out.println(Arrays.toString(newArr));
    }

    //买股票的最佳时机III
    public int maxProfit(int[] prices) {
        int ret = 0;
        int n = prices.length;
        for(int i = 0;i<n-1;i++){
            if(prices[i] < prices[i+1]) ret += (prices[i+1]-prices[i]);

        }
        return ret;
    }
    public static void main6(String[] args) {
        int[] nums = new int[]{1,3,5,2,4,6};
        merge(nums,0,5);
        System.out.println(Arrays.toString(nums));
    }
    public static void main7(String[] args) {
        int[] nums = new int[]{1,3,5,2,4,6};
        qort(nums,0,5);
        System.out.println(Arrays.toString(nums));
    }
    static void qort(int[] nums,int l,int r){
        if(l >= r) return;
//        int x = nums[l+r>>1];
        int x = nums[new Random().nextInt(r-l)+l];
        int i = l-1;
        int j = r+1;
        while(i < j){
            do i++;while(nums[i] < x);
            do j--;while(nums[j] > x);
            if(i < j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        qort(nums,l,j);
        qort(nums,j+1,r);


    }
    static void merge(int[] nums,int l,int r){
        if(l >= r) return;
        int mid = l +r >>1;
        int i = l;
        int j = mid+1;
        merge(nums,l,mid);
        merge(nums,mid+1,r);
        int[] temp = new int[r-l+1];
        int k = 0;
        while(i <= mid && j <= r){
            if(nums[i] < nums[j]) temp[k++] = nums[i++];
            else temp[k++] = nums[j++];
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= r) temp[k++] = nums[j++];
        for(i = l,j = 0;i<r;i++,j++){
            nums[i] = temp[j];
        }
    }
    //分割平衡字符串
    public int balancedStringSplit(String s) {
        int n = s.length();
        int balance = 0;
        int ret = 0;
        for(int i = 0;i<n;i++){
            char ch = s.charAt(i);
            if(ch == 'L') balance++;
            else balance--;
            if(balance == 0) ret++;
        }
        return ret;
    }
    public static void main4(String[] args) {
        List<Integer> list = new ArrayList<>();
    }
    public static void main3(String[] args) {
        Integer[] arr = {1, 5, 2, 8, 3};

        Arrays.sort(arr, Comparator.reverseOrder());

        System.out.println(Arrays.toString(arr));
    }
}
public class Test17 {
    //计算布尔二叉树的值
//    public boolean evaluateTree(TreeNode root) {
//        if(root.left == null) return root.val == 0 ?false : true;
//        boolean left = evaluateTree(root.left);
//        boolean right = evaluateTree(root.right);
//        return root.val == 2?left || right:left&&right;
//    }
    public static void main4(String[] args) {
        Integer[] arr = new Integer[]{1,3,5,2,4,6};
        Arrays.sort(arr,Comparator.reverseOrder() );
//        Arrays.sort(arr, Comparator.reverseOrder());
    }
    public static void main2(String[] args) {
        String s1 = new String("123");
        String s3 = "123".intern();
        String s2 = "123";
        System.out.println(s3 == s2);
    }
    static int[] e = new int[1_0000];
    static int[] n = new int[1_0000];
    static int index;
    //head表示的是头指针的位置 , 注意是索引 , 不是元素
    //-1表示空
    static int head = -1;

    static void add_head(int x){
        e[index] = x;
        n[index] = head;
        head = index;
        index++;
    }
    public static void main1(String[] args) {
        Arrays.fill(n,-1);
        add_head(1);
        add_head(2);
        add_head(3);
        add_head(4);
        int cur = head;
        while(cur != -1){
            System.out.println(e[cur]);
            cur = n[cur];
        }
    }
}
